graph = {}
# 开始节点与邻居节点、结束节点
graph["start"] = {}
graph["start"]["a"] = 5
graph["start"]["b"] = 2
graph["fin"] = {}

# 当前节点与邻居节点
graph["a"] = {}
graph["a"]["c"] = 4
graph["a"]["d"] = 2

graph["b"] = {}
graph["b"]["a"] = 8
graph["b"]["d"] = 7

graph["c"] = {}
graph["c"]["d"] = 6
graph["c"]["fin"] = 3

graph["d"] = {}
graph["d"]["fin"] = 1

infinity = float("inf")
# 初始开销
costs = {}
costs["a"] = graph["start"]["a"]
costs["b"] = graph["start"]["b"]
# costs["c"] = infinity
# costs["d"] = infinity
# costs["fin"] = infinity

# 父节点存储
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

process = []


def find_lowest_node(costs):  # 找出每个节点开销最小的节点
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:  # costs = {"a":5,"b":2}
        cost = costs[node]
        if cost < lowest_cost and node not in process:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node


node = find_lowest_node(costs)

while node is not None:  # 找到开销最小的节点到下一个节点的开销，并与到达该节点的开销进行比较
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        m = None
        try:
            m = costs[n]
        except:
            m = infinity
        finally:
            if m > new_cost:
                costs[n] = new_cost
                parents[n] = node

    process.append(node)
    node = find_lowest_node(costs)

print(parents)
